// Algorithms for calculating strongly-connected components of a DFA.
// They are designed to be memory efficient and use at most few bytes
// of additional memory for each DFA node.

#include "grate/dfa.h"
#include "grate/scc_builder.h"
#include "grate/util/bit_vector.h"
#include "grate/util/stack.h"

namespace growth_rate {

// TODO(samsonov): Add support for improved Tarjan algorithm
//                 (assuming DFA has single scc)

/* static */
SccPartition *SccBuilder::build_scc_naive(const DFAInterface *dfa) {
  size_t dfa_size = dfa->size();
  SccPartition *result = new SccPartition(dfa_size);

  ScopedArray<int> enter_time(dfa_size);
  enter_time.clear();
  ScopedArray<int> father(dfa_size);
  Stack<int> node_stack(dfa_size);
  BitVector in_stack(dfa_size);
  BitVector has_improvement(dfa_size);
  ScopedArray<uint8_t> next_edge(dfa_size);
  next_edge.clear();

  int ctime = 1;
  int cver = DFAInterface::StartNode;
  enter_time[cver] = ctime;
  father[cver] = DFAInterface::UnknownNode;
  node_stack.push(cver);
  in_stack.set(cver, true);
  while (cver >= DFAInterface::StartNode) {
    uint8_t cedge = next_edge[cver];

    if (cedge > 0) {
      // Use result from son.
      int pver = dfa->get_next(cver, cedge - 1);
      if (pver >= DFAInterface::StartNode && father[pver] == cver &&
          enter_time[pver] < enter_time[cver]) {
        enter_time[cver] = enter_time[pver];
        has_improvement.set(cver, true);
      }
    }

    if (cedge == dfa->alphabet_size()) {
      // We are done with the node, check if it's a root of scc and return
      // to father.
      if (!has_improvement.get(cver)) {
        CHECK(!node_stack.is_empty());
        if (node_stack.top() == cver && !dfa->has_loop(cver)) {
          // Node is not a part of scc.
          in_stack.set(cver, false);
          node_stack.pop();
        } else {
          result->scc_number_++;
          int pver;
          do {
            pver = node_stack.pop();
            in_stack.set(pver, false);
            result->scc_[pver] = result->scc_number_;
          } while (pver != cver);
        }
      }
      cver = father[cver];
      continue;
    }

    // Try to visit adjacent node.
    next_edge[cver]++;
    int nver = dfa->get_next(cver, cedge);
    if (nver < DFAInterface::StartNode) continue;
    if (enter_time[nver] == 0) {
      // Forward edge (new node).
      ctime++;
      enter_time[nver] = ctime;
      father[nver] = cver;
      node_stack.push(nver);
      in_stack.set(nver, true);
      cver = nver;
      continue;
    } else if (in_stack.get(nver) && enter_time[nver] < enter_time[cver]) {
      // Backward edge.
      enter_time[cver] = enter_time[nver];
      has_improvement.set(cver, true);
    }
  }

  return result;
}

void DFAInterface::leave_single_scc(const SccPartition *scc_partition) {
  CHECK_EQ(1, scc_partition->scc_number());

  size_t dfa_size = size();
  ScopedArray<int> new_id(dfa_size);

  // Find new numbers of nodes in scc.
  size_t scc_size = 0;
  for (size_t node = StartNode; node < dfa_size; node++) {
    new_id[node] = (scc_partition->scc_for_node(node) == 1) ? scc_size++
                                                            : FakeSink;
  }

  for (size_t node = StartNode; node < dfa_size; node++) {
    if (new_id[node] == FakeSink) continue;
    for (uint8_t letter = 0; letter < alphabet_size(); letter++) {
      int orig_next = get_next(node, letter);
      DCHECK(orig_next == FakeSink || orig_next >= StartNode);
      int new_next = (orig_next == FakeSink) ? FakeSink : new_id[orig_next];
      set_next(new_id[node], letter, new_next);
    }
  }

  // Shrik the DFA transition table.
  shrink_size(scc_size);
}

}  // namespace growth_rate
